#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef int DATA_TYPE;
typedef struct node
{
    DATA_TYPE data;
    struct node *next;
} Lnode, *qlist;

// 创建空链表
qlist creat_list();
// 约瑟夫问题
int ysf(qlist H, int m, int n);
// 尾插
int tail_list(qlist H, DATA_TYPE data);
// 遍历
int show_list(qlist H);

int main(int argc, char const *argv[])
{
    qlist list = creat_list();
    int n;
    printf("请输入人数:");
    scanf("%d", &n);
    for (size_t i = 1; i <= n; i++)
    {
        tail_list(list, i);
    }
    show_list(list);

    ysf(list, 3, n);
    printf("最后还剩下:");
    show_list(list);
    return 0;
}

// 创建空链表
qlist creat_list()
{
    qlist list;
    list = (qlist)malloc(sizeof(Lnode));
    list->data = 0;
    list->next = list;
    return list;
}

// 尾插
int tail_list(qlist H, DATA_TYPE data)
{
    if (H == NULL)
    {
        printf("list is error\n");
        return -1;
    }
    qlist phead = H;
    while (phead->next != H)
    {
        phead = phead->next;
    }
    qlist newnode = (qlist)malloc(sizeof(Lnode));
    if (newnode == NULL)
    {
        printf("newnode malloc failed\n");
        return -1;
    }
    newnode->data = data;
    newnode->next = NULL;

    newnode->next = H;
    phead->next = newnode;

    return 0;
}

// 约瑟夫问题
int ysf(qlist H, int m, int n)
{
    if (H == NULL)
    {
        printf("list is error\n");
        return -1;
    }
    if (H->next == NULL)
    {
        printf("list is empty\n");
        return -1;
    }
    qlist phead = H->next;
    while (n != 1)
    {
        int i = 1;
        while ((i + 1) != m) // phead指向要删的前一个位置
        {
            phead = phead->next;
            if (phead == H)
            {
                phead = phead->next;
            }
            i++;
        }
        if (phead->next != H)
        {
            printf("删除的是第%d个人\n", phead->next->data);
            phead->next = phead->next->next;
            phead = phead->next;
        }
        else
        {
            printf("删除的是第%d个人\n", phead->next->next->data);
            phead = phead->next;
            phead->next = phead->next->next;
            phead = phead->next;
        }
        if (phead == H)
        {
            phead = phead->next;
        }
        n--;
    }
}

// 遍历
int show_list(qlist H)
{
    if (H == NULL)
    {
        printf("list is error\n");
        return -1;
    }
    qlist phead = H->next;
    while (phead != H)
    {
        printf("%d\t", phead->data);
        phead = phead->next;
    }
    printf("\n");
    return 0;
}